package com.dapao.dijkstra.utils;

import com.dapao.dijkstra.data.Data;
import com.dapao.dijkstra.model.ArgModel;
import com.dapao.dijkstra.model.PlanModel;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author DuHan on 2022/2/10
 * @version 1.0
 */
public class DijkstraUtils {
    public static List<PlanModel> Dijkstra(String start, String end) {
        // 路线拓扑数据
        List<ArgModel> argList = Data.getArgList();
        // 最终推荐的路线
        List<PlanModel> planList = new ArrayList<>();
        // 设置起点
        PlanModel startP = new PlanModel(new ArrayList<>(), start, 0, true);
        planList.add(startP);
        boolean flag = true;
        while (flag) {
            // 新路线计划集合
            List<PlanModel> newPanList = new ArrayList<>();
            for (PlanModel plan : planList) {
                // 如果此路线的止点不是用户所输入的止点，则继续往下找，plan.getFlag()=true是因为每条路线只查一次，查询完这条路线后，将flag赋值false
                if (!plan.getEnd().equals(end) && plan.getFlag()) {
                    // 当前点可去往的点
                    List<ArgModel> tList = argList.stream()
                            .filter(p -> p.getFname().equals(plan.getEnd()))
                            .collect(Collectors.toList());
                    // 没有可去往的点
                    if (tList.size() == 0) {
                        continue;
                    }
                    for (ArgModel arg : tList) {
                        // 到下一个点的，路径总长
                        int totalArg = plan.getTotalarg() + arg.getArg();
                        // 检查新计划的集合里也有去往这个点的，如果有的话比较一下长度，只保留路径最短的
                        List<ArgModel> newArgList = new ArrayList<>(plan.getArgList());
                        newArgList.add(arg);
                        PlanModel _plan = new PlanModel(newArgList, arg.getTname(), totalArg, true);
                        newPanList.add(_plan);
                    }
                }
                // 查询标识，每条路线只遍历一次
                plan.setFlag(false);
            }
            // 未发现新路线，结束循环
            if (newPanList.size() == 0) {
                flag = false;
            }
            for (PlanModel newPlan : newPanList) {
                List<PlanModel> list = planList.stream()
                        .filter(p -> p.getEnd().equals(newPlan.getEnd()) && newPlan.getTotalarg() > p.getTotalarg())
                        .collect(Collectors.toList());
                if (list.size() == 0) {
                    planList.add(newPlan);
                }
            }
        }
        return planList.stream()
                .filter(p -> p.getEnd().equals(end))
                .collect(Collectors.toList());
    }


    public static void main(String[] args) {
        List<PlanModel> list = Dijkstra("A", "F");
        System.out.println("共有" + list.size() + "条路线");
        for (int i = 0; i < list.size(); i++) {
            PlanModel planModel = list.get(i);
            System.out.println("第" + (i + 1) + "条，总距离：" + planModel.getTotalarg());
            planModel.getArgList().forEach(p -> {
                System.out.println("由" + p.getFname() + "至" + p.getTname() + "距离：" + p.getArg());
            });
            System.out.println("************");
        }
    }
}
